# -*- coding: utf-8 -*-            
# @Time : 2023/8/22 23:03
# @Author  : lining
# @FileName: 冗余连接.py
"""
https://leetcode.cn/problems/redundant-connection/     深度优先遍历
输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]
优化：O(n)找到边
"""

class FindCycle():
    def __init__(self):
        # 图的节点数
        self.n = 0
        # 有环标记
        self.has_cycle = False
        self.cycle= []

    # 获取这个图有几个节点
    def getnode(self, edges):
        for i in edges:
            self.n = max(self.n, max(i))

    # 获取每个节点能去的边
    def get_to_edg(self, edges):
        self.to_edg = {}
        for i in edges:
            if i[0] not in self.to_edg:
                self.to_edg[i[0]] = [i[1]]
            else:
                self.to_edg[i[0]].append(i[1])
            # 边是双向的
            if i[1] not in self.to_edg:
                self.to_edg[i[1]] = [i[0]]
            else:
                self.to_edg[i[1]].append(i[0])
            # 已经遍历过的节点，每递归完一次就把他重置
            self.visited = {}
            # 每加一条边就dfs一次，has_cycle变成true就是有环，就返回这条边
            self.dfs(i[0], 0)
            if self.has_cycle:
                print(i)
                return

    # 深度优先遍历--找环
    def dfs(self, current, father):
        """
        :param current: 当前走的点
        :param father: 当前点的父节点，0代表没有
        :return:
        """
        # 这个点已经遍历过，如果已经遍历过就不再遍历
        self.visited[current] = True
        # 在to边数组遍历，找到环
        for i in self.to_edg[current]:
            # 类似，1-2，2-1这种不算环，要跳过
            if i == father:
                continue
            # 这个节点还没遍历过，就递归
            if i not in self.visited:
                self.dfs(i, current)
            # 有环
            else:
                self.has_cycle = True


# edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
# edges = [[1,2], [1,3], [2,3]]
edges = [[2,7],[7,8],[3,6],[2,5],[6,8],[4,8],[2,8],[1,8],[7,10],[3,9]]
a = FindCycle()
a.get_to_edg(edges)
# a.dfs(1,0)
# print(a.has_cycle)
# print(get_to_edg(edges))
# print(getnode(edges))

